package stack.middle;

import java.util.Stack;

/**
 * 1. 问题描述
 *      栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，
 *      但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。
 *      当栈为空时，peek返回 -1。
 *
 * 2. 算分分析
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
class SortedStack {

    private Stack<Integer> stack; // 普通的栈
    private Stack<Integer> support; // 定义辅助栈利用辅助栈进行排序


    public SortedStack() {
        this.stack = new Stack<>(); // 初始化普通栈
        this.support = new Stack<>(); // 初始化辅助栈
    }

    public void push(int val) {
        stack.push(val);
        // 对栈进行排序
        while(!stack.isEmpty()) {
            int curTop = stack.pop(); // 取出当前栈顶元素
            if(support.isEmpty()) {
                // 如果辅助栈为空
                support.push(curTop);
            } else {
                // 如果辅助栈不空，进行比较
                while(!support.isEmpty() && curTop < support.peek()) {
                    stack.push(support.pop());
                }
                // 退出循环，将当前元素入栈
                support.push(curTop);
            }
        }
        // 将support中的元素重新放回到stack中
        while(!support.isEmpty()) {
            stack.push(support.pop());
        }
    }

    public void pop() {
        if(!stack.isEmpty()) {
            stack.pop();
        }
    }

    public int peek() {
        if(!stack.isEmpty()) {
            return stack.peek();
        }
        return -1;
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }
}


@SuppressWarnings("all")
public class 排序栈 {
    public static void main(String[] args) {

    }


}
